Usenet 1993 July/InfoMagic USENET CD-ROM July 1993.ISO/sources/misc/volume8/packdisk

Text File | 1989-10-08 | 17.5 KB | 643 lines

Newsgroups: comp.sources.misc
subject: v08i093: System V disk compactor
from: [e-mail] (Brandon S. Allbery - comp.sources.misc)
Reply-To: [e-mail] (Andy Fyfe)

Posting-number: Volume 8, Issue 93
Submitted-by: [e-mail] (Andy Fyfe)
Archive-name: packdisk

The hard disk on my 3b1 reached an intolerable level of fragmentation,
so I wrote this program to do an in situ reorganization of the disk.
The end result is all files and directories are contiguous, and the
free space is collected at the end of the disk.  The program makes great
efforts to leave the disk in a "safe" state at all times (with the
execption of the free list, which isn't rebuilt until the end, though
an "fsck -s" will rebuild it should the program be terminated early).

Though this program was developed on a 3b1, it was written with
portability in mind (yes, I know -- you can stop laughing now!).
Perhaps other systems with the System V file system (inherited from
V7?) can also use the program, or adapt it to their needs.

This program has been successfully run on my system.  I don't promise
that it will run correctly on any system -- including another 3b1.
Use it at your own risk!

Andy Fyfe
            [e-mail]
            [e-mail]
            [e-mail]    (...!ames!elroy!cit-vax!andy)

#! /bin/sh
# This is a shell archive.  Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file".  To overwrite existing
# files, type "sh file -c".  You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g..  If this archive is complete, you
# will see the following message at the end:
#        "End of shell archive."
# Contents:  README COPYRIGHT Makefile packdisk.c
# Wrapped by andy@marmot on Sat Oct  7 19:51:41 1989
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'README' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'README'\"
else
echo shar: Extracting \"'README'\" \(1486 characters\)
sed "s/^X//" >'README' <<'END_OF_FILE'
XThis program rearranges the files and directories on a disk
Xso that they appear contiguously.  This is to counteract the
Xfragmentation that occurs after a time under System V.  After
Xthe program finishes all the free space will be collected at
Xthe end of the disk.
X
XThis program was written on an AT&T 3b1 (running unix version 3.5).
XWhile the program was written with portability in mind, it is *not*
Xguaranteed to run on *any* machine, not even the 3b1.  It has,
Xhowever, worked for me.
X
XYou should run fsck before running this program, and again after
Xit's done, just to be sure!
X
XThe program is *slow*.  However, the disk is updated after *every*
Xblock is moved, so the file system should be in a consistent state
Xif the program is halted for any reason (except for the free list,
Xwhich is not rebuilt until the very end).
X
XI don't guarantee that this program won't destroy your disk.
XMake sure you have a backup just in case!!!
X
XTo run the program, simply give the disk device as its only
Xargument.  The program will normally ensure that the given name
Xis a character special device.  If compiled with '-DDEBUG', this
Xcheck is eliminated.  This allows, for example, you to "dd" a
Xfloppy to a disk file (say /tmp/disk) and then run the program
Xwith '/tmp/disk' as its argument.  When running on a real disk,
Xthe disk in question *must* *not* be mounted!!!
X
XRemember:  THIS PROGRAM IS POTENTIALLY VERY DANGEROUS.  Use it
Xat your own risk.
X
X                Andrew Fyfe
X                [e-mail]
END_OF_FILE
if test 1486 -ne `wc -c <'README'`; then
    echo shar: \"'README'\" unpacked with wrong size!
fi
# end of 'README'
fi
if test -f 'COPYRIGHT' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'COPYRIGHT'\"
else
echo shar: Extracting \"'COPYRIGHT'\" \(1026 characters\)
sed "s/^X//" >'COPYRIGHT' <<'END_OF_FILE'
X/*
X * Copyright (c) Andrew Fyfe, 1989
X * All rights reserved.
X * Written by Andrew Fyfe.
X *
X * Permission is granted to anyone to use this software for any purpose on
X * any computer system, and to alter it and redistribute it freely, subject
X * to the following restrictions:
X *
X * 1. The author is not responsible for the consequences of use of this
X *    software, no matter how awful, even if they arise from flaws in it.
X *
X * 2. The origin of this software must not be misrepresented, either by
X *    explicit claim or by omission.  Since few users ever read sources,
X *    credits must appear in the documentation.
X *
X * 3. Altered versions must be plainly marked as such, and must not be
X *    misrepresented as being the original software.  Since few users
X *    ever read sources, credits must appear in the documentation.
X *
X * 4. This notice may not be removed or altered.
X */
X
X /*
X  * This notice is copied from that included with cnews, which was
X  * written (mostly) by Geoffrey Collyer and Henry Spencer.
X  */
END_OF_FILE
if test 1026 -ne `wc -c <'COPYRIGHT'`; then
    echo shar: \"'COPYRIGHT'\" unpacked with wrong size!
fi
# end of 'COPYRIGHT'
fi
if test -f 'Makefile' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'Makefile'\"
else
echo shar: Extracting \"'Makefile'\" \(129 characters\)
sed "s/^X//" >'Makefile' <<'END_OF_FILE'
XCC = gcc -Wall
XCFLAGS = -O # -DDEBUG
XLDFLAGS = # -shlib
X
Xpackdisk: packdisk.o
X    $(CC) $(CFLAGS) $(LDFLAGS) -o packdisk packdisk.o
END_OF_FILE
if test 129 -ne `wc -c <'Makefile'`; then
    echo shar: \"'Makefile'\" unpacked with wrong size!
fi
# end of 'Makefile'
fi
if test -f 'packdisk.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'packdisk.c'\"
else
echo shar: Extracting \"'packdisk.c'\" \(11393 characters\)
sed "s/^X//" >'packdisk.c' <<'END_OF_FILE'
X/*
X *
X * This program takes a disk and makes all the files and directories,
X * and the free list, contiguous.
X *
X *                         Andrew Fyfe
X *                        7 October 1989
X *
X *                        [e-mail]
X */
X
X#include <sys/filsys.h>
X#include <sys/ino.h>
X#include <sys/stat.h>
X#include <stdio.h>
X#include <stdlib.h>
X
X#define NUM_ADDR    13
X#define FIRST_INDIR    10   /* 0-9 direct, 10 single, 11 double, 12 triple */
X#define NUM_INDIR    (NUM_ADDR - FIRST_INDIR)
X
Xchar *cmd_name;
Xint disk, dev;
X
Xstruct filsys filsys;
X
Xstruct dinode ino;    /* current working inode, and its number */
Xino_t w_ino;
X
Xchar *inode_block;    /* block containing last read/written inode */
Xdaddr_t w_ino_blk;    /* and its number */
X
Xchar *indir[NUM_INDIR];        /* current working indirect blocks */
Xdaddr_t w_indir[NUM_INDIR];    /* and their numbers */
X
Xdaddr_t next_fill;    /* next (sequential) block to fill */
X
Xchar *inode_table;    /* a cache of the entire inode section of the disk */
X
Xlong *map;    /* a map from block numbers to referencing inode/indir block */
X
Xstatic void read_superblk(void);
Xstatic void write_superblk(void);
Xstatic void map_inode(ino_t inode);
Xstatic void update_map(long map_entry, daddr_t block, int level);
Xstatic void read_block(daddr_t block, void *buf);
Xstatic void write_block(daddr_t block, void *buf);
Xstatic void read_inode(ino_t inode, struct dinode *buf);
Xstatic void write_inode(ino_t inode, struct dinode *buf);
Xstatic void move_block(daddr_t from, daddr_t to);
Xstatic void move_inode(ino_t inode);
Xstatic void move_indirect(daddr_t block, int level);
Xstatic void make_hole(void);
Xstatic void rebuild_free_list(void);
X
Xextern void l3tol(long *, char *, int length);
Xextern void ltol3(char *, long *, int length);
X
Xvoid
Xmain(int argc, char *argv[])
X{
X    ino_t inode, total_inodes;
X    daddr_t block;
X    int i;
X    char *ctime(long *);
X#ifndef DEBUG
X    struct stat statb;
X    extern int stat(const char *, struct stat *);
X#endif
X
X    cmd_name = argv[0];
X
X    if (argc != 2) {
X    fprintf(stderr, "%s: Usage: %s <file system>\n",
X        cmd_name, cmd_name);
X    exit(1);
X    }
X
X#ifndef DEBUG
X    if (stat(argv[1], &statb) < 0) {
X    fprintf(stderr, "%s: can't stat %s: ", cmd_name, argv[1]);
X    perror("");
X    exit(1);
X    }
X    if ((statb.st_mode & S_IFMT) != S_IFCHR) {
X    fprintf(stderr, "%s: %s is not a character device\n",
X        cmd_name, argv[1]);
X    exit(1);
X    }
X#endif
X
X    disk = open(argv[1], 2, 0);
X    if (disk < 0) {
X    fprintf(stderr, "%s: can't open %s: ", cmd_name, argv[1]);
X    perror("");
X    exit(1);
X    }
X
X    read_superblk();
X
X    total_inodes = (filsys.s_isize - FsITOD(dev, ROOTINO)) * FsINOPB(dev);
X    fprintf(stderr, "File system: name: \"%.6s\", pack: \"%.6s\"\n",
X    filsys.s_fname, filsys.s_fpack);
X    fprintf(stderr, "\tlast modified on %s", ctime(&filsys.s_time));
X    fprintf(stderr,
X    "\ttotal inodes = %d, data blocks = %d, total = %d blocks\n",
X    total_inodes, filsys.s_fsize - filsys.s_isize, filsys.s_fsize);
X    fprintf(stderr, "\tfree blocks = %d, free inodes = %d\n",
X    filsys.s_tfree, filsys.s_tinode);
X
X    for (i = 0; i < NUM_INDIR; ++i) {
X    w_indir[i] = 0;
X    indir[i] = malloc(FsBSIZE(dev));
X    if (indir[i] == 0) {
X        fprintf(stderr, "%s: can't malloc indir buffer space: ", cmd_name);
X        perror("");
X        exit(1);
X    }
X    }
X    w_ino = 0;
X
X    map = calloc(filsys.s_fsize, sizeof(*map));
X    if (map == 0) {
X    fprintf(stderr, "%s: can't calloc map: ", cmd_name);
X    perror("");
X    exit(1);
X    }
X
X    inode_table = malloc(filsys.s_isize * FsBSIZE(dev));
X    if (inode_table == 0) {
X    fprintf(stderr, "%s: can't malloc space for inode table\n", cmd_name);
X    w_ino_blk = 0;
X    inode_block = malloc(FsBSIZE(dev));
X    if (inode_block == 0) {
X        fprintf(stderr, "%s: can't malloc inode buffer space: ", cmd_name);
X        perror("");
X        exit(1);
X    }
X    }
X    else
X    for (block = FsITOD(dev, ROOTINO); block < filsys.s_isize; ++block)
X        read_block(block, &inode_table[block * FsBSIZE(dev)]);
X
X    fprintf(stderr, "mapping...");
X    for (inode = ROOTINO; inode <= total_inodes; ++inode)
X    map_inode(inode);
X    fprintf(stderr, "done\n");
X
X    next_fill = filsys.s_isize;
X    for (inode = ROOTINO; inode <= total_inodes; ++inode)
X    move_inode(inode);
X
X    fprintf(stderr, "\nrebuilding the free list\n");
X    rebuild_free_list();
X
X    fprintf(stderr, "*** Run fsck to check out the disk!!!\n");
X
X    close(disk);
X    exit(0);
X}
X
Xstatic void
Xread_superblk(void)
X{
X    if (lseek(disk, SUPERBOFF, 0) != SUPERBOFF) {
X    fprintf(stderr, "%s: can't seek to superblock: ", cmd_name);
X    perror("");
X    exit(1);
X    }
X    if (read(disk, &filsys, sizeof(filsys)) != sizeof(filsys)) {
X    fprintf(stderr, "%s: can't read superblock: ", cmd_name);
X    perror("");
X    exit(1);
X    }
X    if (filsys.s_magic != FsMAGIC) {
X    fprintf(stderr, "%s: invalid superblock magic number\n", cmd_name);
X    exit(1);
X    }
X    dev = (filsys.s_type == Fs2b) ? Fs2BLK : 0;
X}
X
Xstatic void
Xwrite_superblk(void)
X{
X    lseek(disk, SUPERBOFF, 0);
X    if (write(disk, &filsys, sizeof(filsys)) != sizeof(filsys)) {
X    fprintf(stderr, "%s: can't write superblock: ", cmd_name);
X    perror("");
X    exit(1);
X    }
X}
X
Xstatic void
Xmap_inode(ino_t inode)
X{
X    int type, i;
X    long block[NUM_ADDR];
X
X    read_inode(inode, &ino);
X    if (ino.di_mode == 0)
X    return;
X    type = ino.di_mode & S_IFMT;
X    if (type == S_IFCHR || type == S_IFBLK)
X    return;
X
X    l3tol(block, ino.di_addr, NUM_ADDR);
X    for (i = 0; i < NUM_ADDR; ++i)
X    if (block[i] != 0)
X        update_map(inode, block[i],
X        (i < FIRST_INDIR) ? 0 : (i - FIRST_INDIR + 1));
X}
X
Xstatic void
Xupdate_map(long map_entry, daddr_t block, int level)
X{
X    int i;
X
X    if (map[block] != 0) {
X    fprintf(stderr, "%s: duplicate block %d in %d and %d\n",
X        cmd_name, block, map[block], map_entry);
X    exit(1);
X    }
X    map[block] = map_entry;
X
X    if (level == 0)
X    return;
X
X    --level;
X    read_block(block, indir[level]);
X    for (i = 0; i < FsNINDIR(dev); ++i)
X    if (((daddr_t *)indir[level])[i] != 0)
X        update_map(-block, ((daddr_t *)indir[level])[i], level);
X}
X
Xstatic void
Xread_block(daddr_t block, void *buf)
X{
X    lseek(disk, block * FsBSIZE(dev), 0);
X    if (read(disk, buf, FsBSIZE(dev)) != FsBSIZE(dev)) {
X    fprintf(stderr, "%s: can't read block %d: ", cmd_name, block);
X    perror("");
X    exit(1);
X    }
X}
X
Xstatic void
Xwrite_block(daddr_t block, void *buf)
X{
X    lseek(disk, block * FsBSIZE(dev), 0);
X    if (write(disk, buf, FsBSIZE(dev)) != FsBSIZE(dev)) {
X    fprintf(stderr, "%s: can't write block %d: ", cmd_name, block);
X    perror("");
X    exit(1);
X    }
X}
X
Xstatic void
Xread_inode(ino_t inode, struct dinode *ino)
X{
X    daddr_t block;
X
X    block = FsITOD(dev, inode);
X    if (inode_table == 0) {
X    if (w_ino_blk != block) {
X        w_ino_blk = block;
X        read_block(block, inode_block);
X    }
X    *ino = ((struct dinode *)inode_block)[FsITOO(dev, inode)];
X    }
X    else {
X    *ino = ((struct dinode *)&inode_table[block * FsBSIZE(dev)])
X        [FsITOO(dev, inode)];
X    }
X}
X
Xstatic void
Xwrite_inode(ino_t inode, struct dinode *ino)
X{
X    daddr_t block;
X
X    block = FsITOD(dev, inode);
X    if (inode_table == 0) {
X    if (w_ino_blk != block) {
X        w_ino_blk = block;
X        read_block(block, inode_block);
X    }
X    ((struct dinode *)inode_block)[FsITOO(dev, inode)] = *ino;
X    write_block(block, inode_block);
X    }
X    else {
X    ((struct dinode *)&inode_table[block * FsBSIZE(dev)])
X        [FsITOO(dev, inode)] = *ino;
X    write_block(block, &inode_table[block * FsBSIZE(dev)]);
X    }
X}
X
Xstatic void
Xmove_block(daddr_t from, daddr_t to)
X{
X    char buffer[FsBSIZE(dev)];
X    daddr_t block;
X
X    if (map[to] != 0)
X    make_hole();
X
X    read_block(from, buffer);
X    write_block(to, buffer);
X
X    map[to] = map[from];
X    map[from] = 0;
X
X    for (block = filsys.s_isize; block < filsys.s_fsize; ++block)
X    if (map[block] == -from)
X        map[block] = -to;
X}
X
Xstatic void
Xmove_inode(ino_t inode)
X{
X    int type, i;
X    long block[NUM_ADDR];
X
X    read_inode(inode, &ino);
X    w_ino = inode;
X    if (ino.di_mode == 0)
X    return;
X    type = ino.di_mode & S_IFMT;
X    if (type == S_IFCHR || type == S_IFBLK)
X    return;
X
X    fprintf(stderr, "moving inode %d (size %d)                         \r",
X    inode, ino.di_size);
X
X    l3tol(block, ino.di_addr, NUM_ADDR);
X    for (i = 0; i < NUM_ADDR; ++i) {
X    if (block[i] == 0)
X        continue;
X    if (block[i] != next_fill) {
X        move_block(block[i], next_fill);
X        l3tol(block, ino.di_addr, NUM_ADDR);
X        block[i] = next_fill;
X        ltol3(ino.di_addr, block, NUM_ADDR);
X        write_inode(inode, &ino);
X    }
X    ++next_fill;
X    }
X
X    for (i = FIRST_INDIR; i < NUM_ADDR; ++i)
X    move_indirect(block[i], i-FIRST_INDIR);
X}
X
Xstatic void
Xmove_indirect(daddr_t block, int level)
X{
X    int i;
X
X    if (block == 0)
X    return;
X
X    read_block(block, indir[level]);
X    w_indir[level] = block;
X
X    for (i = 0; i < FsNINDIR(dev); ++i) {
X    if (((daddr_t *)indir[level])[i] == 0)
X        continue;
X    if (((daddr_t *)indir[level])[i] != next_fill) {
X        move_block(((daddr_t *)indir[level])[i], next_fill);
X        ((daddr_t *)indir[level])[i] = next_fill;
X        write_block(block, indir[level]);
X    }
X    ++next_fill;
X    }
X
X    if (level == 0)
X    return;
X
X    for (i = 0; i < FsNINDIR(dev); ++i)
X    move_indirect(((daddr_t *)indir[level])[i], level-1);
X}
X
Xstatic void
Xmake_hole(void)
X{
X    char t_indir[FsBSIZE(dev)];
X    daddr_t *p_indir;
X    struct dinode t_ino, *p_ino;
X    long block[NUM_ADDR];
X    daddr_t back;
X    int i;
X
X    back = filsys.s_fsize - 1;
X    while (next_fill < back && map[back] != 0)
X    --back;
X
X    if (next_fill >= back) {
X    fprintf(stderr, "%s: can't find a free block for %d\n",
X        cmd_name, next_fill);
X    exit(1);
X    }
X
X    move_block(next_fill, back);
X
X    if (map[back] < 0) {
X    block[0] = -map[back];
X    for (i = 0; i < NUM_INDIR; ++i)
X        if (block[0] == w_indir[i])
X        break;
X    if (i < NUM_INDIR) {
X        p_indir = (daddr_t *)indir[i];
X    }
X    else {
X        p_indir = (daddr_t *)t_indir;
X        read_block(block[0], t_indir);
X    }
X    for (i = 0; i < FsNINDIR(dev); ++i) {
X        if (p_indir[i] == next_fill) {
X        p_indir[i] = back;
X        break;
X        }
X    }
X    if (i == FsNINDIR(dev)) {
X        fprintf(stderr,
X        "%s: panic: can't find %d in indirect block %d\n",
X        cmd_name, next_fill, -map[back]);
X        exit(1);
X    }
X    write_block(block[0], p_indir);
X    }
X    else {
X    if (map[back] == w_ino) {
X        p_ino = &ino;
X    }
X    else {
X        p_ino = &t_ino;
X        read_inode(map[back], &t_ino);
X    }
X    l3tol(block, p_ino->di_addr, NUM_ADDR);
X    for (i = 0; i < NUM_ADDR; ++i) {
X        if (block[i] == next_fill) {
X        block[i] = back;
X        ltol3(p_ino->di_addr, block, NUM_ADDR);
X        break;
X        }
X    }
X    if (i == NUM_ADDR) {
X        fprintf(stderr, "%s: panic: can't find %d in inode %d\n",
X        cmd_name, next_fill, map[back]);
X        exit(1);
X    }
X    write_inode(map[back], p_ino);
X    }
X}
X
Xstatic void
Xrebuild_free_list(void)
X{
X    int free_size, nfree;
X    daddr_t free[NICFREE], block;
X    char buf[FsBSIZE(dev)];
X
X    free_size = filsys.s_fsize - next_fill;
X    if (free_size != filsys.s_tfree) {
X    fprintf(stderr, "%s: free list changed size from %d to %d\n",
X        cmd_name, filsys.s_tfree, free_size);
X    exit(1);
X    }
X
X    nfree = 1;
X    memset(free, 0, sizeof(free));
X    memset(buf, 0, sizeof(buf));
X
X    for (block = filsys.s_fsize - 1; block >= next_fill; --block) {
X    if (nfree == NICFREE) {
X        ((daddr_t *)buf)[0] = nfree;
X        memcpy(&((daddr_t *)buf)[1], free, sizeof(free));
X        write_block(block, buf);
X        nfree = 0;
X        memset(free, 0, sizeof(free));
X    }
X    free[nfree++] = block;
X    }
X
X    filsys.s_nfree = nfree;
X    memcpy(&filsys.s_free, free, sizeof(free));
X    write_superblk();
X}
END_OF_FILE
if test 11393 -ne `wc -c <'packdisk.c'`; then
    echo shar: \"'packdisk.c'\" unpacked with wrong size!
fi
# end of 'packdisk.c'
fi
echo shar: End of shell archive.
exit 0